package com.algorithm.learning.base.动态规划;

import java.util.Stack;

/**
 * @program: algorithm-learning
 * @description: 条件：在不利用其他数据结构的情况下，把一个栈逆序
 * @author: YuKai Fan
 * @create: 2024/9/2 21:39
 **/
public class 逆序栈 {

    /**
     * 参考逆序栈步骤图：/img/逆序栈步骤图.png
     * @param stack
     */
    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        // 这个值肯定是原始栈的栈底元素
        int i = func(stack);
        reverse(stack);
        stack.push(i);
    }

    public static int func(Stack<Integer> stack) {
        Integer result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int last = func(stack);
            stack.push(result);
            return last;
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(2);
        stack.push(1);
        reverse(stack);
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
